RSA的解密

加密時我們把pt^e = ct mod N 得到ct
解密時把ct^d = pt mod N,
也就是pt^(ed) mod N,
已知ed = 1 mod phi(N)
能寫成ed = 1 + h⋅phi(N),其中h為任意正數
那麼有pt^(ed) = pt^(1 + h⋅phi(N)) = pt⋅pt^(h⋅phi(N)) = pt(pt^phi(N))^h
當pt跟N互質時
pt(pt^phi(N))^h 拿去 mod N
根據歐拉定理會得到
pt(1)^h mod N
也就成功從ct回到pt了

費馬小定理

在介紹歐拉定理之前,先來介紹它的前身,也就是費馬小定理（英語：Fermat's little theorem）
西元1636年由皮埃爾·德·費馬所發表的一個數學定理,簡介如下:
設a為一個整數而p為一個質數,其中a和p互質(也就是a和p的最大公因數為1)
那麼 a^(p-1) =1 mod p 會成立

簡單的證明

如果存在ma = na mod p,因為a和p互質,所以m = n mod p
那麼有一個集合{1a,2a,3a,....(p-1)a}拿去 mod p,會轉換成{1,2,3,4,....(p-1)} mod p
再來把集合內的元素相乘
(1a)(2a)(3a)...((p-1)a) mod p = 1⋅2⋅3.....⋅(p-1) mod p
接者把左邊的a(共(p-1)個)全部提出來,就會變成
a^(p-1)⋅(p-1)! = (p-1)! mod p
由於p是質數所以(p-1)!和p也會互質
就能把兩邊的(p-1)!消掉,也就得到了 a^(p-1) = 1 mod p

歐拉定理（數論）

歐拉(歐拉歐拉)定理是費馬小定理的延伸
今天只要a和n互質,n不一定要是質數
那麼 a^phi(n) = 1 mod n
- 歐拉函數 phi(n) 是小於等於n的正整數中與n互質的數的數目

求模反元素

模反元素是在模樹運算(mod)中一種元素
而當b為a的模反元素時(在mod n的條件下)
a⋅b = 1 mod n
RSA中的私鑰d就是在給定公鑰e和模數n後求e的模反元素
其中的條件是a要和n互質
我們能用擴展歐幾里得算法來求出模反元素
給定a,n
帶入等式
ax+ny = g
而g為a,n的最大公因數
當g為1時(a,n互質)
ax+ny = 1 拿去mod n
得到
ax+ny = ax = 1 mod n
因為mod n,所以n的倍數(ny)會不見
而此時的x就是a的模反元素